/* 栈和队列练习题参考答案（C语言实现）*/
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>

// ======================= 栈基础实现 =======================

// 基于数组的栈实现
#define MAX_STACK_SIZE 100

typedef struct {
    int data[MAX_STACK_SIZE];
    int top;
} Stack;

void initStack(Stack* stack) {
    stack->top = -1;
}

bool isStackEmpty(Stack* stack) {
    return stack->top == -1;
}

bool isStackFull(Stack* stack) {
    return stack->top == MAX_STACK_SIZE - 1;
}

bool push(Stack* stack, int value) {
    if (isStackFull(stack)) {
        return false;
    }
    stack->data[++stack->top] = value;
    return true;
}

int pop(Stack* stack) {
    if (isStackEmpty(stack)) {
        return -1; // 表示错误
    }
    return stack->data[stack->top--];
}

int peek(Stack* stack) {
    if (isStackEmpty(stack)) {
        return -1; // 表示错误
    }
    return stack->data[stack->top];
}

int stackSize(Stack* stack) {
    return stack->top + 1;
}

// ======================= 队列基础实现 =======================

// 基于循环数组的队列实现
#define MAX_QUEUE_SIZE 100

typedef struct {
    int data[MAX_QUEUE_SIZE];
    int front;
    int rear;
    int count;
} Queue;

void initQueue(Queue* queue) {
    queue->front = 0;
    queue->rear = 0;
    queue->count = 0;
}

bool isQueueEmpty(Queue* queue) {
    return queue->count == 0;
}

bool isQueueFull(Queue* queue) {
    return queue->count == MAX_QUEUE_SIZE;
}

bool enqueue(Queue* queue, int value) {
    if (isQueueFull(queue)) {
        return false;
    }
    queue->data[queue->rear] = value;
    queue->rear = (queue->rear + 1) % MAX_QUEUE_SIZE;
    queue->count++;
    return true;
}

int dequeue(Queue* queue) {
    if (isQueueEmpty(queue)) {
        return -1; // 表示错误
    }
    int value = queue->data[queue->front];
    queue->front = (queue->front + 1) % MAX_QUEUE_SIZE;
    queue->count--;
    return value;
}

int front(Queue* queue) {
    if (isQueueEmpty(queue)) {
        return -1; // 表示错误
    }
    return queue->data[queue->front];
}

int queueSize(Queue* queue) {
    return queue->count;
}

// ======================= 栈练习解答 =======================

// 练习2：括号匹配检查
bool isValidParentheses(char* s) {
    Stack stack;
    initStack(&stack);
    
    int len = strlen(s);
    for (int i = 0; i < len; i++) {
        char c = s[i];
        
        // 如果是开括号，入栈
        if (c == '(' || c == '[' || c == '{') {
            push(&stack, c);
        }
        // 如果是闭括号，检查是否匹配
        else if (c == ')' || c == ']' || c == '}') {
            if (isStackEmpty(&stack)) {
                return false; // 没有匹配的开括号
            }
            
            char top = pop(&stack);
            if ((c == ')' && top != '(') || 
                (c == ']' && top != '[') || 
                (c == '}' && top != '{')) {
                return false; // 括号不匹配
            }
        }
    }
    
    // 最后检查栈是否为空
    return isStackEmpty(&stack);
}

// 练习3：栈元素排序
void sortStack(Stack* stack) {
    Stack tempStack;
    initStack(&tempStack);
    
    while (!isStackEmpty(stack)) {
        // 弹出原栈顶元素
        int temp = pop(stack);
        
        // 将临时栈中所有大于temp的元素移回原栈
        while (!isStackEmpty(&tempStack) && peek(&tempStack) > temp) {
            push(stack, pop(&tempStack));
        }
        
        // 将temp放入临时栈
        push(&tempStack, temp);
    }
    
    // 将临时栈中的元素移回原栈（此时已排序）
    while (!isStackEmpty(&tempStack)) {
        push(stack, pop(&tempStack));
    }
}

// 练习4：最小栈实现
typedef struct {
    Stack dataStack;  // 存储所有元素
    Stack minStack;   // 辅助栈，存储当前最小值
} MinStack;

void initMinStack(MinStack* minStack) {
    initStack(&minStack->dataStack);
    initStack(&minStack->minStack);
}

void minStackPush(MinStack* minStack, int value) {
    // 数据栈正常入栈
    push(&minStack->dataStack, value);
    
    // 最小栈为空或当前值小于等于最小栈顶元素时，入栈
    if (isStackEmpty(&minStack->minStack) || value <= peek(&minStack->minStack)) {
        push(&minStack->minStack, value);
    }
}

void minStackPop(MinStack* minStack) {
    if (!isStackEmpty(&minStack->dataStack)) {
        // 如果出栈元素等于当前最小值，最小栈也要出栈
        if (peek(&minStack->dataStack) == peek(&minStack->minStack)) {
            pop(&minStack->minStack);
        }
        pop(&minStack->dataStack);
    }
}

int minStackTop(MinStack* minStack) {
    return peek(&minStack->dataStack);
}

int minStackGetMin(MinStack* minStack) {
    return peek(&minStack->minStack);
}

// 练习6：计算后缀表达式
int evaluatePostfix(char* expression) {
    Stack stack;
    initStack(&stack);
    
    int len = strlen(expression);
    for (int i = 0; i < len; i++) {
        char c = expression[i];
        
        // 跳过空格
        if (c == ' ') {
            continue;
        }
        
        // 如果是数字，解析并入栈
        if (isdigit(c)) {
            int num = 0;
            // 解析多位数字
            while (i < len && isdigit(expression[i])) {
                num = num * 10 + (expression[i] - '0');
                i++;
            }
            i--; // 回退一位
            push(&stack, num);
        }
        // 如果是运算符，弹出两个操作数进行计算
        else {
            int operand2 = pop(&stack);
            int operand1 = pop(&stack);
            int result;
            
            switch (c) {
                case '+':
                    result = operand1 + operand2;
                    break;
                case '-':
                    result = operand1 - operand2;
                    break;
                case '*':
                    result = operand1 * operand2;
                    break;
                case '/':
                    result = operand1 / operand2; // 假设不会除以零
                    break;
                default:
                    printf("不支持的运算符: %c\n", c);
                    return -1;
            }
            
            push(&stack, result);
        }
    }
    
    // 最终栈中应该只剩一个元素，即结果
    return pop(&stack);
}

// 练习7：使用栈实现队列
typedef struct {
    Stack inputStack;  // 用于入队操作
    Stack outputStack; // 用于出队操作
} QueueUsingStacks;

void initQueueUsingStacks(QueueUsingStacks* queue) {
    initStack(&queue->inputStack);
    initStack(&queue->outputStack);
}

void queuePush(QueueUsingStacks* queue, int value) {
    push(&queue->inputStack, value);
}

int queuePop(QueueUsingStacks* queue) {
    // 如果输出栈为空，将输入栈的所有元素转移到输出栈
    if (isStackEmpty(&queue->outputStack)) {
        while (!isStackEmpty(&queue->inputStack)) {
            push(&queue->outputStack, pop(&queue->inputStack));
        }
    }
    
    return pop(&queue->outputStack);
}

int queuePeek(QueueUsingStacks* queue) {
    // 如果输出栈为空，将输入栈的所有元素转移到输出栈
    if (isStackEmpty(&queue->outputStack)) {
        while (!isStackEmpty(&queue->inputStack)) {
            push(&queue->outputStack, pop(&queue->inputStack));
        }
    }
    
    return peek(&queue->outputStack);
}

bool queueEmpty(QueueUsingStacks* queue) {
    return isStackEmpty(&queue->inputStack) && isStackEmpty(&queue->outputStack);
}

// ======================= 队列练习解答 =======================

// 练习2：使用队列实现栈
typedef struct {
    Queue q1; // 主要队列
    Queue q2; // 辅助队列
} StackUsingQueues;

void initStackUsingQueues(StackUsingQueues* stack) {
    initQueue(&stack->q1);
    initQueue(&stack->q2);
}

void stackPush(StackUsingQueues* stack, int value) {
    // 将新元素入队到q2
    enqueue(&stack->q2, value);
    
    // 将q1的所有元素出队并入队到q2
    while (!isQueueEmpty(&stack->q1)) {
        enqueue(&stack->q2, dequeue(&stack->q1));
    }
    
    // 交换q1和q2的角色
    Queue temp = stack->q1;
    stack->q1 = stack->q2;
    stack->q2 = temp;
}

int stackPop(StackUsingQueues* stack) {
    return dequeue(&stack->q1);
}

int stackTop(StackUsingQueues* stack) {
    return front(&stack->q1);
}

bool stackEmpty(StackUsingQueues* stack) {
    return isQueueEmpty(&stack->q1);
}

// 练习4：最近请求次数
typedef struct {
    Queue pingQueue;
} RecentCounter;

void initRecentCounter(RecentCounter* counter) {
    initQueue(&counter->pingQueue);
}

int ping(RecentCounter* counter, int t) {
    // 入队当前请求
    enqueue(&counter->pingQueue, t);
    
    // 移除过期的请求（超过3000毫秒）
    while (!isQueueEmpty(&counter->pingQueue) && front(&counter->pingQueue) < t - 3000) {
        dequeue(&counter->pingQueue);
    }
    
    // 返回队列大小，即最近3000毫秒内的请求数
    return queueSize(&counter->pingQueue);
}

// 练习6：队列的最大值（简化版，使用两个队列）
typedef struct {
    Queue dataQueue;  // 存储所有元素
    Queue maxQueue;   // 单调递减队列，存储可能的最大值
} MaxQueue;

void initMaxQueue(MaxQueue* maxQueue) {
    initQueue(&maxQueue->dataQueue);
    initQueue(&maxQueue->maxQueue);
}

void maxQueueEnqueue(MaxQueue* maxQueue, int value) {
    // 数据队列正常入队
    enqueue(&maxQueue->dataQueue, value);
    
    // 维护单调递减队列：移除所有小于value的元素
    while (!isQueueEmpty(&maxQueue->maxQueue) && 
           front(&maxQueue->maxQueue) < value) {
        dequeue(&maxQueue->maxQueue);
    }
    enqueue(&maxQueue->maxQueue, value);
}

void maxQueueDequeue(MaxQueue* maxQueue) {
    if (!isQueueEmpty(&maxQueue->dataQueue)) {
        int frontValue = front(&maxQueue->dataQueue);
        dequeue(&maxQueue->dataQueue);
        
        // 如果出队的元素等于当前最大值，单调队列也出队
        if (frontValue == front(&maxQueue->maxQueue)) {
            dequeue(&maxQueue->maxQueue);
        }
    }
}

int maxQueueGetMax(MaxQueue* maxQueue) {
    return front(&maxQueue->maxQueue);
}

// 练习8：二叉树的层序遍历（简化模拟）
// 这里我们用数组模拟二叉树的层序遍历
void levelOrderTraversal(int* tree, int size) {
    if (size == 0) return;
    
    Queue queue;
    initQueue(&queue);
    
    // 根节点入队
    enqueue(&queue, 0); // 0是根节点的索引
    
    int levelCount = 1;
    int currentLevel = 0;
    
    printf("层序遍历结果：\n");
    printf("层 %d: ", currentLevel);
    
    while (!isQueueEmpty(&queue)) {
        int index = dequeue(&queue);
        printf("%d ", tree[index]);
        
        // 左子节点索引
        int left = 2 * index + 1;
        if (left < size && tree[left] != -1) { // -1表示空节点
            enqueue(&queue, left);
        }
        
        // 右子节点索引
        int right = 2 * index + 2;
        if (right < size && tree[right] != -1) {
            enqueue(&queue, right);
        }
        
        levelCount--;
        if (levelCount == 0) {
            levelCount = queueSize(&queue);
            currentLevel++;
            if (!isQueueEmpty(&queue)) {
                printf("\n层 %d: ", currentLevel);
            }
        }
    }
    printf("\n");
}

// 练习12：数据流中的移动平均值
typedef struct {
    Queue windowQueue;
    int windowSize;
    double sum;
} MovingAverage;

void initMovingAverage(MovingAverage* ma, int size) {
    initQueue(&ma->windowQueue);
    ma->windowSize = size;
    ma->sum = 0.0;
}

double next(MovingAverage* ma, int val) {
    // 如果队列已满，移除队首元素并更新总和
    if (queueSize(&ma->windowQueue) >= ma->windowSize) {
        ma->sum -= dequeue(&ma->windowQueue);
    }
    
    // 入队新元素并更新总和
    enqueue(&ma->windowQueue, val);
    ma->sum += val;
    
    // 返回平均值
    return ma->sum / queueSize(&ma->windowQueue);
}

// 测试函数
int main() {
    // 测试括号匹配
    printf("===== 测试括号匹配 =====\n");
    char* test1 = "()[]{}";
    char* test2 = "([)]";
    char* test3 = "{[]}";
    printf("%s: %s\n", test1, isValidParentheses(test1) ? "有效" : "无效");
    printf("%s: %s\n", test2, isValidParentheses(test2) ? "有效" : "无效");
    printf("%s: %s\n", test3, isValidParentheses(test3) ? "有效" : "无效");
    
    // 测试栈排序
    printf("\n===== 测试栈排序 =====\n");
    Stack stack;
    initStack(&stack);
    push(&stack, 3);
    push(&stack, 1);
    push(&stack, 4);
    push(&stack, 2);
    
    printf("排序前栈顶元素: %d\n", peek(&stack));
    sortStack(&stack);
    printf("排序后栈顶元素: %d\n", peek(&stack));
    printf("排序后栈元素（出栈顺序）: ");
    while (!isStackEmpty(&stack)) {
        printf("%d ", pop(&stack));
    }
    printf("\n");
    
    // 测试最小栈
    printf("\n===== 测试最小栈 =====\n");
    MinStack minStack;
    initMinStack(&minStack);
    minStackPush(&minStack, 3);
    minStackPush(&minStack, 5);
    minStackPush(&minStack, 2);
    minStackPush(&minStack, 1);
    printf("当前最小值: %d\n", minStackGetMin(&minStack));
    minStackPop(&minStack);
    printf("出栈后最小值: %d\n", minStackGetMin(&minStack));
    
    // 测试后缀表达式求值
    printf("\n===== 测试后缀表达式求值 =====\n");
    char* postfix1 = "3 4 + 2 * 7 /";
    char* postfix2 = "5 1 2 + 4 * + 3 -";
    printf("%s = %d\n", postfix1, evaluatePostfix(postfix1));
    printf("%s = %d\n", postfix2, evaluatePostfix(postfix2));
    
    // 测试最近请求次数
    printf("\n===== 测试最近请求次数 =====\n");
    RecentCounter counter;
    initRecentCounter(&counter);
    printf("ping(1): %d\n", ping(&counter, 1));
    printf("ping(100): %d\n", ping(&counter, 100));
    printf("ping(3001): %d\n", ping(&counter, 3001));
    printf("ping(3002): %d\n", ping(&counter, 3002));
    
    // 测试移动平均值
    printf("\n===== 测试移动平均值 =====\n");
    MovingAverage ma;
    initMovingAverage(&ma, 3);
    printf("next(1): %.2f\n", next(&ma, 1));
    printf("next(10): %.2f\n", next(&ma, 10));
    printf("next(3): %.2f\n", next(&ma, 3));
    printf("next(5): %.2f\n", next(&ma, 5));
    
    // 测试二叉树层序遍历（用数组模拟，-1表示空节点）
    printf("\n===== 测试二叉树层序遍历 =====\n");
    int tree[] = {3, 9, 20, -1, -1, 15, 7}; // 模拟示例中的树
    levelOrderTraversal(tree, 7);
    
    return 0;
}

/*
## 代码说明

1. **基础数据结构**：
   - 实现了基于数组的栈和循环队列
   - 提供了基本的操作函数如初始化、判空、判满、插入、删除等

2. **栈练习解答**：
   - 练习2（括号匹配）：使用栈存储开括号，遇到闭括号时检查匹配
   - 练习3（栈排序）：使用辅助栈实现栈的排序
   - 练习4（最小栈）：使用辅助栈同步存储当前最小值
   - 练习6（后缀表达式求值）：使用栈存储操作数，遇到运算符时弹出计算
   - 练习7（栈实现队列）：使用两个栈，一个用于入队，一个用于出队

3. **队列练习解答**：
   - 练习2（队列实现栈）：使用两个队列，入队时重新排列保证栈的顺序
   - 练习4（最近请求次数）：使用队列保存请求时间，移除过期请求
   - 练习6（队列最大值）：使用单调队列维护可能的最大值
   - 练习8（二叉树层序遍历）：使用队列实现，按层打印节点
   - 练习12（移动平均值）：使用队列维护窗口内的元素，动态计算平均值

4. **主函数**：提供了各个功能的测试代码，展示如何使用这些实现

## 使用建议

1. 将此代码保存为 `.c` 文件并使用C编译器编译运行
2. 可以根据需要修改测试用例或添加更多功能
3. 对于更复杂的实现（如双端队列、线程安全队列等），可以参考现有代码自行扩展
4. 在实际练习时，建议先尝试独立解决问题，再参考此答案

注意：代码中简化了一些错误处理，实际应用中可能需要更完善的错误处理机制。*/